TrueTime API in Spanner

TrueTime is a highly available distributed clock service. With TrueTime, applications can produce timestamps that increase monotonically. For example, if the generation of the timestamp $T$ ends before that of the timestamp $T'$ begins, then the resultant timestamp $T'$will be bigger than the previous timestamp $T$ (with in an error bound). This is guaranteed for all servers and at any given time.

Spanner assigns timestamps to each transaction using the TrueTime API. The timestamp is the exact time Spanner considered the transaction to commit. Spanner's multi-version concurrency control guarantees the ordering of transactions on timestamps. It allows clients to execute consistent reads over the database, even when spread across different cloud regions, without blocking writes.

Let's dive into the details of the TrueTime API.

TrueTime API methods#

As per Spanner's published paper, the methods that the TrueTime API allows are as follows:

The argument t is of the TTstamp type. TrueTime reports an interval of time, TTinterval, instead of an exact timestamp. The interval with bounded time uncertainty is represented directly in TrueTime. All endpoints of TTinterval must be of the TTstamp type. Upon calling TT.now(), we'll get back a TTinterval (earliest and latest values) that includes the precise moment that we want. The values are the earliest possible and latest possible timestamps. As per Spanner's published paper, the time epoch is analogous to the UNIX time epoch with leap-second smearing. $\epsilon$ represents instantaneous error bound, and $\bar\epsilon$ represents average error bound. $\epsilon$ is half of the interval's width.

For an event, $e$, consider the absolute time $t_{abs}(e)$. The TrueTime API will guarantee the following for an invocation:

where $e_{now}$ is the invocation event.

Real-time dependency in TrueTime#

The key here is waiting to commit. In a real system, we want to wait for the minimum time. So we now need to do two things:

1. We need to quantify the uncertainty so we know how long we must wait.

2. We have to keep the uncertainty as small as possible so that our waiting time is as short as possible.

Controlling uncertainty in TrueTime#

TrueTime relies on atomic clocks and Global Positioning System (GPS) coordinates to keep accurate time. Due to their varied failure mechanisms, TrueTime employs two-time reference sources. It is possible for the integrity of the GPS reference source to be compromised by a number of factors, including antenna and receiver failures, local radio interference, correlated failures, and GPS outages. Due to frequency inaccuracies, atomic clocks can drift dramatically over extended periods of time. The failure modes of atomic clocks can be independent of the GPS and one another.

Each data center has its own set of time manager machines, and each machine has its copy of the time follower daemon. Most managers use GPS receivers with dedicated antennas and keep their systems physically apart to lessen the impact of antenna failures, radio interference, and spoofing. Armageddon managers are the surviving managers that have atomic clocks. The price of an atomic clock is comparable to that of a Global Positioning System (GPS) manager. The various managers' time standards are often checked against one another. Every manager compares the speed at which its reference advances time to that of its local clock. If the two times are significantly out of sync, then the manager removes itself. Using a conservative estimate of the worst-case scenario for clock drift, Armageddon managers advocate for an ever-increasing interval between synchronizations. GPS managers announce uncertainty that is approximately zero.

Note: Though Google calls the time manager machine a "time master machine", the Armageddon manager an "Armageddon master", and GPS manager a "GPS master" in their research paper on Spanner, we will use the terms "time manager machine", "Armageddon manager", and "GPS manager" to refer to the same things.

Each daemon will poll multiple managers to lessen its dependence on any one manager and, therefore, its susceptibility to failure. Some are handpicked GPS managers from close-by data centers, while others come from further afield, along with a few Armageddon managers. The clocks of the local machine and non-liars are synchronized. Daemons use Marzullo's algorithm's modified version to identify and remove the liars. Computers with frequency excursions larger than the worst-case bound are booted to prevent faulty local clocks.

The following slides explain how TrueTime’s time manager servers work with the GPS and atomic clocks in multiple data centers. In every data center, we have time handlers. GPS time managers have GPS receivers attached, and few have atomic clocks. When a client needs to call the TrueTime API, the client communicates to the local daemon. The daemon (a background service that runs on all nodes in the data center) mostly contacts GPS time managers and sometimes contacts atomic clock time managers to get the redundancy of different time references. Marzullo's algorithm is run, which intersects time intervals to determine a time reference. The API gives an interval from the earliest to the latest.

Minimize uncertainty in TrueTime#

A daemon alerts of increasing time uncertainty between synchronizations. The value comes from using the worst-case scenario for possible local clock drift. It is also influenced by the unpredictability of the time taken by managers and the lag in receiving information from them. This will result in a sawtooth function of time. Throughout every poll period, the function ranges between 1 ms to 7 ms. On average, it is 4 ms. The sawtooth boundaries of 0 to 6 ms result from the present settings for the poll interval (30 seconds) and the applied drift rate (200 microseconds/second). One millisecond is lost because of slow messages reaching the time managers. In the presence of setbacks, deviations from this sawtooth are possible. For instance, when the time manager is unavailable on rare occasions, it can result in data center-wide increases in $\epsilon$. Similarly, occasionally isolated $\epsilon$ spikes can result from overburdened machines or network connectivity.

The following slides show the progress of epsilon on a node over time that forms a sawtooth each time the client requests to the TrueTime API.

Summary#

There are two key insights in this lesson:

1. While it is true that perfectly synchronizing clocks in a distributed system is very hard, we can control the amount of uncertainty in clock readings. Using special hardware, we can reduce such uncertainty.

2. The TrueTime API seems innocuous, but it is very powerful. It enables us to do what a vector clock does under certain conditions (having timestamps with causality in a large system where the difference between the two timestamps is large than clock uncertainty). Vector clocks are expensive in space use, but TrueTime does the same work using a simple timestamp. We will see in later lessons that TrueTime provides more than causality because its timestamp is related to the wall clock time.

We learned how the TrueTime API works. It seems that TrueTime allows Spanner to overrule the CAP theorem by providing high availability and consistency simultaneously. In the next lesson, we will discuss the CAP theorem and Spanner.